package com.itheima.datastructure.linkedlist;

/**
 * 检测环的入口
 */
public class E11Leetcode142 {


    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next; //龟走一步
            fast = fast.next.next; //兔走两步
            if (slow == fast) { // 第一次相遇

                //第二阶段，乌返回起点
                slow = head;

                while (true) {
                    //如果两个已经相遇，所以需要先判断
                    if (slow == fast) { // 第二次相遇
                        return slow;
                    }
                    fast = fast.next; //龟走一步
                    slow = slow.next;//兔走一步
                }
            }
        }
        return null;

    }


    public static void main(String[] args) {
        // 构造一个带环链表
        ListNode n12 = new ListNode(12, null);
        ListNode n11 = new ListNode(11, n12);
        ListNode n10 = new ListNode(10, n11);
        ListNode n9 = new ListNode(9, n10);
        ListNode n8 = new ListNode(8, n9);
        ListNode n7 = new ListNode(7, n8);
        ListNode n6 = new ListNode(6, n7);
        ListNode n5 = new ListNode(5, n6);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);

        n12.next = n8;

        System.out.println(new E11Leetcode142().detectCycle(n1).val);
    }
}
